import { StringDecoder } from "string_decoder";

/**
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 * 删除链表的倒数第N个节点
 * @param head
 * @param n
 */
const removeNthFromEnd = (
  head: ListNode | null,
  n: number
): ListNode | null => {
  // 链表为空或者链表只有一个节点, 只能返回空
  if (head === null || head.next === null) return null;

  // 两个指针都指向头节点
  let first: ListNode | null = head,
    second: ListNode | null = head,
    len = 0,
    preN = n

  // 刚开始的时候先让first先走, 走到n步的时候, 让first和second同时走
  while (first !== null) {
    if (n < 0) {
      // 当n为0的时候, 就开始往下遍历
      second = second!.next;
    }

    first = first.next;
    n--;
    // 记录节点数量
    len++
  }

  let newHead = head;
  // 当second为空的时候, first刚好指向的是倒数第n个节点的前驱节点
  if (second === head && len === preN) {
    // 删除的是头节点s
    newHead = head.next;
  } else  {
    second!.next = second!.next ? second!.next.next : null;
  }

  return newHead;
};

// 使用数组保存节点
const removeNthFromEnd2 = (
  head: ListNode | null,
  n: number
): ListNode | null => {
  // 链表为空
  if (head === null) return null;

  // 保存从头到尾的每一个节点
  const linkeds: ListNode[] = [];

  let h: ListNode | null = head;

  // 直到链表不为空
  while (h !== null) {
    linkeds.push(h);
    h = h.next;
  }

  // 默认头节点就是head
  let newHead = head;
  // 删除节点的位置
  const place = linkeds.length - n;

  if (place === 0) {
    // 删除的是头节点
    newHead = linkeds[1] || null;
  } else {
    // 删除的不是头节点
    linkeds[place - 1].next = linkeds[place].next;
  }
  return newHead;
};
